package com.dy.队列.优先级队列;

import com.dy.线性表.链表.Node;
import com.dy.队列.IQueue;

public class PriorityQueue implements IQueue {



    private Node front, rear;

    @Override
    public void clear() {
        front = rear = null;
    }

    @Override
    public boolean isEmpty() {
        return front == rear;
    }

    @Override
    public int length() {
        Node p = front;
        int len = 0;
        while (p != null) {
            len++;
            p = p.next;
        }
        return len;
    }

    @Override
    public Object peek() {
        if (front == null) return null;
        return front.data;
    }

    @Override
    public void offer(Object x) throws Exception {
        PriorityQData pd = (PriorityQData) x;
        Node s = new Node(pd);
        if (front == null) {
            front = rear = s;
        } else {
            Node p = front, q = front;
            while (p != null && pd.priority >= ((PriorityQData) p.data).priority) {
                q = p;
                p = p.next;
            }

            if (p == null) {
                rear.next = s;
                rear = s;
            }
            else if(p==front){
                s.next = front;
                front = s;
            }
            else{
                q.next = s;
                s.next = p;
            }

        }

    }

    @Override
    public Object poll() {
        if (front == null) return null;
        Node p = front;
        front = front.next;
        return p.data;
    }

    public void display(){
        Node p = front;
        if(p!=null){
            while(p!=rear.next){
                PriorityQData pqd = (PriorityQData)p.data;
                System.out.print(pqd.elem+" "+pqd.priority);
                System.out.println();
                p=p.next;
            }
        }
    }
}
